package tree;

import java.util.LinkedList;

//todo
public class RecoverBinarySearchTree99 {

    //迭代方式实现中序遍历
//    public void recoverTree(TreeNode root) {
//        if(root==null){
//            return;
//        }
//        LinkedList<TreeNode> stack = new LinkedList<>();
//        stack.push(root);
//        while (!stack.isEmpty()){
//            TreeNode node = stack.pop();
//            if(node.left!=null){
//                stack.push(node.left);
//            }
//        }
//
//    }






    //1、递归方式实现中序遍历
//    TreeNode pre;
//    TreeNode x;
//    TreeNode y;
//
//    public void recoverTree(TreeNode root) {
//        preOrder(root);
//        int tmp = x.val;
//        x.val = y.val;
//        y.val = tmp;
//    }
//
//    private void preOrder(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        preOrder(root.left);
//
//        if (pre != null) {
//            if (pre.val > root.val) {
//                if(x==null){
//                    x = pre;
//                }
//                y = root;
//            }
//        }
//        pre = root;
//
//        preOrder(root.right);
//    }

}
